The present invention relates to a cache architecture for variable length data. When used in a processor core, the cache architecture can support storage of variable length instruction segments and can retrieve multiple instruction segments (or portions thereof in a single clock cycle. The cache architecture also contributes to minimized fragmentation of the instruction segments.
FIG. 1 is a block diagram illustrating the process of program execution in a conventional processor. Program execution may include three stages: front end 110, execution 120 and memory 130. The front-end stage 110 performs instruction pre-processing. Front end processing 110 is designed with the goal of supplying valid decoded instructions to an execution unit 120 with low latency and high bandwidth. Front-end processing 110 can include instruction prediction, decoding and renaming. As the name implies, the execution stage 120 performs instruction execution. The execution stage 120 typically communicates with a memory 130 to operate upon data stored therein.
Conventionally, front end processing 110 may build instruction segments from stored program instructions to reduce the latency of instruction decoding and to increase front-end bandwidth. Instruction segments are sequences of dynamically executed instructions that are assembled into logical units. The program instructions may have been assembled into the instruction segment from non-contiguous regions of an external memory space but, when they are assembled in the instruction segment, the instructions appear in program order. The instruction segment may include instructions or uops (micro-instructions).
A trace is perhaps the most common type of instruction segment. Typically, a trace may begin with an instruction of any type. Traces have a single entry, multiple exit architecture. Instruction flow starts at the first instruction but may exit the trace at multiple points, depending on predictions made at branch instructions embedded within the trace. The trace may end when one of number of predetermined end conditions occurs, such as a trace size limit, the occurrence of a maximum number of conditional branches or the occurrence of an indirect branch or a return instruction. Traces typically are indexed by the address of the first instruction therein.
Other instruction segments are known. The inventors have proposed an instruction segment, which they call an xe2x80x9cextended block,xe2x80x9d that has a different architecture than the trace. The extended block has a multiple-entry, single-exit architecture. Instruction flow may start at any point within an extended block but, when it enters the extended block, instruction flow must progress to a terminal instruction in the extended block. The extended block may terminate on a conditional branch, a return instruction or a size limit. The extended block may be indexed by the address of the last instruction therein.
A xe2x80x9cbasic blockxe2x80x9d is another example of an instruction segment. It is perhaps the most simple type of instruction segment available. The basic block may terminate on the occurrence of any kind of branch instruction, including an unconditional branch. The basic block may be characterized by a single-entry, single-exit architecture. Typically, the basic block is indexed by the address of the first instruction therein.
Regardless of the type of instruction segment used in a processor 110, the instruction segment typically is cached for later use. Reduced -latency is achieved when program flow returns to the instruction segment because the instruction segment may store instructions already assembled in program order. The instructions in the cached instruction segment may be furnished to the execution stage 120 faster than they could be furnished from different locations in an ordinary instruction cache.
Caches typically have a predetermined width; the width determines the maximum amount of data that could be retrieved from cache in a single clock cycle. The width of a segment cache typically determines the maximum size of the instruction segment. To retrieve data, a cache address is supplied to the cache, which causes contents of a cache entry to be driven to a cache output.
Because instruction segments are terminated based on the content of the instructions from which they are built, the instruction segments typically have variable length. So, while a segment cache may have capacity to store, say, 16 instructions per segment, the average length of the instructions segments may be much shorter than this maximum length. In fact, in many typical applications, an average instruction segment length is slightly more than 8 instructions per segment. If these instruction segments were stored in a traditional segment cache, the capacity of the segment cache may be under-utilized; the 8-instruction segment would prevent excess capacity in a much larger cache line from storing other data. Further, a traditional segment cache would output the smaller instruction segment, when addressed, even though it may have the capacity for much larger data items.
Accordingly, there exists a need in the art for a cache structure that stores variable length data and can output data with higher utilization than would be provided by a traditional cache.